|
The Bellman–Ford algorithm is an algorithm that computes shortest paths from a single source vertex to all of the other vertices in a weighted digraph. It is slower than Dijkstra's algorithm for the same problem, but more versatile, as it is capable of handling graphs in which some of the edge weights are negative numbers. The algorithm is named after two of its developers, Richard Bellman and Lester Ford, Jr., who published it in 1958 and 1956, respectively; however, Edward F. Moore also published the same algorithm in 1957, and for this reason it is also sometimes called the Bellman–Ford–Moore algorithm.〔 Negative edge weights are found in various applications of graphs, hence the usefulness of this algorithm. If a graph contains a "negative cycle" (i.e. a cycle whose edges sum to a negative value) that is reachable from the source, then there is no ''cheapest'' path: any path can be made cheaper by one more walk around the negative cycle. In such a case, the Bellman–Ford algorithm can detect negative cycles and report their existence. 〔 ==Algorithm== Like Dijkstra's Algorithm, Bellman–Ford is based on the principle of relaxation, in which an approximation to the correct distance is gradually replaced by more accurate values until eventually reaching the optimum solution. In both algorithms, the approximate distance to each vertex is always an overestimate of the true distance, and is replaced by the minimum of its old value with the length of a newly found path. However, Dijkstra's algorithm uses a priority queue to greedily select the closest vertex that has not yet been processed, and performs this relaxation process on all of its outgoing edges; by contrast, the Bellman–Ford algorithm simply relaxes ''all'' the edges, and does this times, where is the number of vertices in the graph. In each of these repetitions, the number of vertices with correctly calculated distances grows, from which it follows that eventually all vertices will have their correct distances. This method allows the Bellman–Ford algorithm to be applied to a wider class of inputs than Dijkstra. Bellman–Ford runs in time, where and are the number of vertices and edges respectively. function BellmanFord(''list'' vertices, ''list'' edges, ''vertex'' source) ::distance := inf // At the beginning , all vertices have a weight of infinity predecessor() := null // And a null predecessor distance() := 0 // Except for the Source, where the Weight is zero ''// Step 2: relax edges repeatedly'' for i from 1 to size(vertices)-1: for each edge (u, v) with weight w in edges: if distance() + w < distance(): distance() := distance() + w predecessor() := u ''// Step 3: check for negative-weight cycles'' for each edge (u, v) with weight w in edges: if distance() + w < distance(): error "Graph contains a negative-weight cycle" return distance[], predecessor[] Simply put, the algorithm initializes the distance to the source to 0 and all other nodes to infinity. Then for all edges, if the distance to the destination can be shortened by taking the edge, the distance is updated to the new lower value. At each iteration that the edges are scanned, the algorithm finds all shortest paths of at most length edges. Since the longest possible path without a cycle can be edges, the edges must be scanned times to ensure the shortest path has been found for all nodes. A final scan of all the edges is performed and if any distance is updated, then a path of length edges has been found which can only occur if at least one negative cycle exists in the graph. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Bellman–Ford algorithm」の詳細全文を読む スポンサード リンク
|